// @before-stub-for-debug-begin
#include <vector>
#include <string>
#include "commoncppproblem787.h"

using namespace std;
// @before-stub-for-debug-end

/*
 * @lc app=leetcode.cn id=787 lang=cpp
 *
 * [787] K 站中转内最便宜的航班
 */

// @lc code=start
class Solution {
private:
    int MAX = 10000 * 101 + 1;

public:
    int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {
        vector<vector<int> > dp(k + 2, vector<int>(n, MAX));
        dp[0][src] = 0;
        for (int i = 1; i < k + 2; ++i) {
            for (auto& flight : flights) {
                int a = flight[0], b = flight[1], cost = flight[2];
                dp[i][b] = min(dp[i][b], dp[i - 1][a] + cost);
            }
        }
        int res = MAX;
        for (int i = 1; i < k + 2; ++i) {
            res = min(res, dp[i][dst]);
        }
        return res == MAX ? -1 : res;
    }
};
// @lc code=end

